//
// Created by francklinson on 2021/7/11 AT 20:40.
//

//现在，我们用一些方块来堆砌一个金字塔。 每个方块用仅包含一个字母的字符串表示。
//
//使用三元组表示金字塔的堆砌规则如下：
//
//对于三元组 ABC ，C 为顶层方块，方块 A 、B 分别作为方块 C 下一层的的左、右子块。当且仅当 ABC 是被允许的三元组，我们才可以将其堆砌上。
//
//初始时，给定金字塔的基层bottom，用一个字符串表示。一个允许的三元组列表allowed，每个三元组用一个长度为 3 的字符串表示。
//
//如果可以由基层一直堆到塔尖就返回 true ，否则返回 false 。
//
//来源：力扣（LeetCode）
//链接：https://leetcode-cn.com/problems/pyramid-transition-matrix
//著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。


#include <utility>
#include <vector>
#include <string>
#include <iostream>
#include <unordered_map>

using namespace std;

class Solution {
private:
    /// 允许的方块 存在hash中
    unordered_map<string, vector<char>> cube;
public:
    bool pyramidTransition(string bottom, vector<string> &allowed) {
        // 根据允许的石块搭配，构建石块hash
        unsigned int n = bottom.size();
        vector<string> tower(n);
        // 最底层
        tower.back() = std::move(bottom);
        for (auto &str:allowed) {
            cube[str.substr(0, 2)].emplace_back(str[2]); // 一个石块的构型
        }
        return DFS(tower, n - 1, 0);
    }

    /// 递归函数
    bool DFS(vector<string> &tower, int r, int c) {
        // 一层结束了
        if (r == c) {
            c = 0;
            --r;
        }
        // 成功到顶层
        if (r == 0) return true;
        // 提取下面的两块
        string need = tower[r].substr(c, 2);
        // 没有这种石块
        if (!cube.count(need)) return false;
        for (auto &alpha:cube[need]) {
            tower[r - 1].push_back(alpha);
            if (DFS(tower, r, c + 1)) return true;
            // 回溯
            tower[r - 1].pop_back();
        }
        return false;
    }


};

int main() {
    vector<string> allowed{"BCG", "CDE", "GEA", "FFF"};
    Solution sol;
    cout << sol.pyramidTransition("BCD", allowed) << endl;
    return 0;
}

